package jjn.acwing.algorithm_basic.chapter1.sort;

import java.util.Scanner;

/**
 * @author Jjn
 * @since 2023/8/20 16:16
 */
public class Acwing788 {
    
    static long mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return 0;
        }
        int mid = l + r >> 1;
        long result = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
        int[] temp = new int[r - l + 1];
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
                result += mid - i + 1;
            }
        }
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= r) {
            temp[k++] = nums[j++];
        }
        for (i = l, j = 0; i <= r; i++, j++) {
            nums[i] = temp[j];
        }
        return result;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int[] nums = new int[i];
        for (int j = 0; j < i; j++) {
            nums[j] = scanner.nextInt();
        }
        long result = mergeSort(nums, 0, nums.length - 1);
        System.out.println(result);
    }
}
